package company;

import java.util.Scanner;

/**
 * 583. 两个字符串的删除操作
 * 给定两个单词 word1 和 word2 ，返回使得 word1 和  word2 相同所需的最小步数。
 *
 * 每步 可以删除任意一个字符串中的一个字符。
 *
 *  
 *
 * 示例 1：
 *
 * 输入: word1 = "sea", word2 = "eat"
 * 输出: 2
 * 解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"
 * 示例  2:
 *
 * 输入：word1 = "leetcode", word2 = "etco"
 * 输出：4
 *  
 * 思路分析
 * 方案1：删除一定次数之后，两个字符串相同，其实可以求这俩字符串的最长公共子串
 * 用两个字符串的长度和-最长公共子串的长度
 * 方案2：
 * 如果i=j,那么删除次数=dp[i-1][j-1]
 * 如果i!=j, 那么删除可能删除i-1，可能删j-1，所以dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+1
 *
 * 这里先实现方案2
 */
public class minDistance {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String word = sc.nextLine();
        String word1 = sc.nextLine();
        System.out.println(minDistance(word, word1));
    }

    public static int minDistance(String word, String word1) {
        int len = word.length();
        int len1 = word1.length();
        int[][] dp = new int[len+1][len1+1];
        // 初始化
        for (int i = 0; i <= len; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= len1; i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= len; i++) {
            for (int j = 1; j <= len1; j++) {
                if(word.charAt(i-1) == word1.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    // 那么删除可能删除i-1，可能删j-1，那么就只能取前面i-1或者前面j-1的删除操作次数
                    dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1])+1;
                }
            }
        }
        return dp[len][len1];
    }
}
